# -*- encoding:utf-8 -*-
import time
import random
import math

# 同一天到达，同一天离开
people=[('Seymour','BOS'),
        ('Franny','DAL'),
        ('Zooey','CAK'),
        ('Walt','MIA'),
        ('Buddy','ORD'),
        ('Les','OMA')]

# New York 的LaGuardia机场
destination='LGA'

flights={}

# [1,4,3,2,7,3,6,3,2,4,5,3]
# 0表示当天第一次航班，1表示当天第2次航班，类推
s=[1,4,3,2,7,3,6,3,2,4,5,3]

#
for line in file('schedule.txt'):
    origin,dest,depart,arrive,price=line.strip().split(',')
    flights.setdefault((origin,dest),[])

    # 将航班详情添加到航班列表中
    flights[(origin,dest)].append((depart,arrive,int(price)))

def getminutes(t):
    x = time.strptime(t,'%H:%M')
    return x[3]*60+x[4]

# 用以解析如下列表：
# [1,4,3,2,7,3,6,3,2,4,5,3]
# 0表示当天第一次航班，1表示当天第2次航班，类推
def printschedule(r):
    for d in range(len(r)/2):
        name=people[d][0]
        origin=people[d][1]
        out=flights[(origin,destination)][r[2*d]]
        ret=flights[(destination,origin)][r[2*d+1]]
        print '%10s%10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin,out[0],out[1],out[2],ret[0],ret[1],ret[2])



# 时间成本函数(涉及条件：价格；每个人在飞机上花费的总时间；在机场等待其他成员到达的时间；汽车租用时间)
def schedulecost(sol):
    totalprice=0
    latestarrival=0
    earlieststep=24*60

    for d in range(len(sol)/2):
        # 得到往程航班和返程航班
        origin = people[d][1]
        outbound = flights[(origin,destination)][int(sol[2*d])]
        returnf = flights[(destination,origin)][int(sol[2*d+1])]

        # 总价格等于所有往程航班和返程航班价格之和
        totalprice+=outbound[2]
        totalprice+=returnf[2]

        # 记录最早离开的时间和最晚到达的时间
        if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
        if earlieststep>getminutes(returnf[0]): earlieststep=getminutes(returnf[0])

    # 每个人必须在机场等待直到最后一个人到达为止
    # 同时他们也必须在相同时间到达，并等候他们的返程航班(因为需要乘坐同一辆汽车用以节约成本)
    totalwait=0
    for d in range(len(sol)/2):
        origin = people[d][1]
        outbound = flights[(origin,destination)][int(sol[2*d])]
        returnf = flights[(destination,origin)][int(sol[2*d+1])]
        totalwait+=latestarrival-getminutes(outbound[1])
        totalwait+=getminutes(returnf[0])-earlieststep

    if earlieststep>latestarrival : totalprice+=50

    return totalprice+totalwait

# print len(flights[('LGA','DAL')])

# 随机搜索
# domain 二元组，分别代表变量最小值和最大值。每个人有10个往程和返程，有6个人所以长度为12
# :[(0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9)]
def randomoptimize(domain,costf):
    best =99999999
    bestr =None
    for i in range(10000):
        # 创建一个随机解（从0,9中随机选一组解）
        r = [random.randint(domain[i][0],domain[i][1])
             for i in range(len(domain))]

        # 得到成本
        cost = costf(r)

        # 与到目前为止的最优解进行比较
        if cost<best:
            best=cost
            bestr=r
    return r

domain = [(0,9)]*(len(people)*2)
# answer = randomoptimize(domain,schedulecost)
# print answer
# print schedulecost(answer)
# printschedule(answer)
#
# 爬山法
def hillclimb(domain,costf):
    # 创建一个随机解：
    sol = [random.randint(domain[i][0],domain[i][1])
           for i in range(len(domain))]

    while 1:
        # 创建相邻解的列表
        neightbor=[]
        for j in range(len(domain)):

            # 在每个方向上相对于原值偏离一点,
            if sol[j] > domain[j][0]:
                # 构造新的列表
                neightbor.append(sol[0:j]+[sol[j]-1]+sol[j+1:])
            if sol[j] < domain[j][1]:
                neightbor.append(sol[0:j]+[sol[j]+1]+sol[j+1:])

        # 从相邻解中寻找最优解
        current=costf(sol)
        best = current
        for j in range(len(neightbor)):
            cost =costf(neightbor[j])
            if cost<best:
                best=cost
                sol=neightbor[j]

        if best==current:
            break

    return sol

# printschedule(hillclimb(domain,schedulecost))
# print schedulecost(hillclimb(domain,schedulecost))

# 退火算法
def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
    # 随机初始化值
    vec = [random.randint(domain[i][0],domain[i][1])
           for i in range(len(domain))]

    while T>0.1:
        # 选择一个索引值
        i=random.randint(0,len(domain)-1)

        # 选择一个改变索引值的方向
        dir=random.randint(-step,step)

        # 创建一个代表题解的新列表，改变其中一个值
        vecb=vec[:]
        vecb[i]+=dir
        if vecb[i]<domain[i][0]: vecb[i]=domain[i][0]
        elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1]

        # 当前成本和新成本
        ea=costf(vec)
        eb=costf(vecb)

        # 它是更好的解吗? 或者是去向最优解的可能的邻接解吗?
        if eb <ea or random.random() < pow(math.e,-(eb-ea)/T) :
            vec=vecb

        T=T*cool

    return vec
# printschedule(annealingoptimize(domain,schedulecost))
# print schedulecost(annealingoptimize(domain,schedulecost))

# 遗传算法
# popsize:种群大小；mutprob：种群新成员中的变异概率；elite：种群中的优解且会传入下一代的部分；
# maxiter寻要运行多少代
def geneticoptimize(domain,costf,popsize=50,step=1,mutprob=0.2,elite=0.2,maxiter=100):

    # 变异操作
    def mutate(vec):
        i = random.randint(0,len(domain)-1)
        if random.random<0.5:
            if vec[i]-step>domain[i][0]:
                vec[i]=vec[i]-step
        else:
            if vec[i]+step<domain[i][1]:
                vec[i]=vec[i]+step
        return vec[0:i]+[vec[i]]+vec[i+1:]

    # 交叉操作
    def crossover(r1,r2):
        i=random.randint(1,len(domain)-2)
        return r1[0:i]+r2[i:]

    # 创建初始种群
    pop=[]
    for i in range(popsize):
        vec = [random.randint(domain[i][0],domain[i][1])
               for i in range(len(domain))]
        pop.append(vec)

    # 每一代有多少胜出者？
    topelite=int(elite*popsize)
    for i in range(maxiter):
        scores=[(costf(v),v) for v in pop]
        scores.sort()
        ranked = [v for (s,v) in scores]

        # 从嘴纯粹的胜出者开始
        pop=ranked[0:topelite-1]

        # 添加变异和配对后的胜出者
        while len(pop)<popsize:
            if random.random()<mutprob:
                # 变异
                c=random.randint(0,topelite-1)
                pop.append(mutate(ranked[c]))

            else :
                # 交叉
                c1=random.randint(0,topelite-1)
                c2=random.randint(0,topelite-1)
                pop.append(crossover(ranked[c1],ranked[c2]))

        print scores[0][0]

    return scores[0][1]

# printschedule(geneticoptimize(domain,schedulecost))